ECC—Error-Correction-Coding is a process by which additional redundant information is appended to a message in order to render the message resilient to errors inflicted on it in the process of transmission and reception or equivalently, during storage and retrieval. This additional information is called the “redundancy”. There are many various ways and algorithms to derive the redundancy, the exact algorithm is not pertinent to this invention, it is enough to note, that the redundancy is computed by the encoder from all of the message's bits.
In the decoder a reverse process occurs, the erroneous message with the redundancy is received and inspected. The errors are identified and fixed (if possible), the redundancy is stripped from the message, and the recovered message is passed to the client.
FIG. 1 illustrates a prior art ECC encoding and ECC decoding process. A message 11 (illustrated as having content 0100111 . . . 1011010) is partitioned into packets m1, m2 . . . mN (collectively denoted 21) that are fed to the first encoder 13(1). The first encoder 13(1) computes redundancies r1, r1, r2 . . . RN (collectively denoted R1 21) for each packet which are appended (“append redundancy”) 14 to the message to provide an encoded message 15. Encoded message 15 is illustrated as having content “0100111 . . . 1011010 . . . 0110” and includes packets m1, m2 . . . mN and redundancies r1, r2 . . . rN.
The encoded message 15 is transmitted or stored in the “error inflicting” channel or media 16 to provide an error containing message 17 {m1, m2 . . . Mn, r1 . . . rN}+{e} (illustrated as having content (0101111 . . . 1010010 . . . 00000). The error containing message 17 is received by the first decoder 18(1). The first decoder 18(1) identifies and fixes the errors if possible. Redundancies are stripped from the data and a recovered message 19 including recovered (error corrected) packets {m1′, m2′, . . . mN′} is fed to the client.
Multi-Dimensional ECC
In a simple case messages i.e. packets are serially fed to the encoder, transmitted, received, and recovered, all in a serial manner. But In order to improve error correction capability it is common to partition the large message into some collection of smaller packets i.e. into a successive series {m1, m2 . . . mN}, then calculate redundancies for each of them i.e. {r11, r12 . . . r1N}, then partition the data again in some other different permutation {n1, n2 . . . nN} (It is possible to have different number of packets in each dimension, i.e. N and K for example in the 2 dimensional case), and compute redundancies for this collection also i.e. {r21, r22 . . . r2N} etc. . . . and repeat this process N times to produce an N dimensional ECC system.
In order to facilitate understanding and simplify the drawings (without any loss of generality) the following explanations will refer to a two-dimensional ECC encoding.
In essence, each bit is encoded in two different packets, which is simply means that each bit participates in the calculation of 2 redundancies one in each “dimension” as described previously for a single dimension. The redundancies then appended to the message and transmitted in a communication system (or stored in a storage system).
For demonstration and simplicity FIG. 2 depicts a pair of encoders that execute two dimensional encoding so that each bit of the message is decoded twice.
First encoder 13(1) gets the original message 11 in order and generates a redundancy (collectively denoted R1 20(1)) for each of the packets m1, m2 . . . mN.
Second encoder 13(2) receives the message after it was reordered in some different permutation, i.e. the second encoder 13(2) gets a different series of packets n0, n1 and generates redundancy (collectively denoted R2 20(2)) for packets n1, n2 . . . nN
Because the encoding is two dimensional—each bit of the message belongs both to some packet ‘m’ in the first dimension and one packet ‘n’ of a second dimension.
To better understand the partition of the message, consider FIG. 3. It depicts the partitioning of message 11 into packets m1 . . . mN 21(1)-21(N). The first dimension simply partitions the data “in order” successively into each appropriate packet.
In contrast—second encoder 13(2) gets a different set of packets i.e. n1, n2 . . . nN (denoted 22(1)-22(N) in FIG. 4) where each successive byte of a packet resides elsewhere in the original data according to some permutation.
Another different and popular representation of the data partitioning and permutation is depicted in an “interleaving diagram”, this depiction also assumes a known and popular permutation. The permutation is achieved using a two dimensional shift register. For simplicity of explanation it is assumed that the shift register is an N*N shift register—thus there are N packets on each dimension—which is only an example as the number of packets per one dimension may differ from a number of packets of another dimension leading to a non-rectangular shift register. FIGS. 6A and 6B depict this permutation, the original message 11 is depicted as being a stream of successive N^2 bytes of data numbered by the order of arrival 1 . . . . N^2 11(1)-11(N^2). Wherein N^2 means N by the power of two.
This successive stream is fed into a two dimensional shift register 30 having N^2 by N^2 cells—to form N^2 columns and N^2 rows. Each cell of the 2 dimensional shift register is marked with its byte number (with respect to the arrival order—illustrated by dashed line 34).
When the shift register is full, data is shifted out horizontally into the second encoder 13(2) (FIG. 2) to form the n1 . . . nN packets 22(1)-22(N), and also shifted vertically into the first encoder 13(1) to form packets m1, m2 mN.
FIGS. 3 and 4 show packets m1 and n1 22(1) and 21(1) respectively and exemplify their byte composition.
On-the-Fly or Streaming/not-Buffered Operation
It is advantageous to design a system that doesn't require buffering all of the data prior to the beginning of encoding. It is much better in terms of latency to start computation at the moment the first byte of the original data arrives, yet it is clear that for example for packet n1 (denoted 22(1) in FIGS. 6A and 6B) the encoder will stall while waiting for byte N+1 (while bytes 2, 3, 4 . . . N are fed to the encoder), which comes right after byte 1 as the second byte of packet 22(1). In the meantime packets n2, n3 . . . are also stalled while the encoder is waiting for the next byte of packet n1.
This latency problem can be solved by employing N encoders as depicted in FIG. 5 encoders 13(1)-13(N−1)—wherein the number of encoders equals the number of packets in the message. First encoder 13(1) starts computation as byte #1 arrives, than stalls until byte #(N+1) (which is the 2nd byte of packet n1) arrives, second encoder 13(2) starts as byte #2 is available etc. . . . .
Note that each encoder retains its state as each one is dedicated for each of the packets.
This solution is expensive, hard to configure and inappropriate for some applications.